package lib

//BinarySearch 二分搜索
func BinarySearch(arr []int, searchVal int) (index int) {
	low := 0
	high := len(arr) - 1

	for low <= high {

		mid := (low + high) / 2
		val := arr[mid]

		if val == searchVal {
			return mid
		} else if val < searchVal {
			low = mid + 1
		} else if val > searchVal {
			high = mid - 1
		} else {
			return
		}
	}

	return
}

//输入的数组必须是按顺序排列的，不能是随机排列
//二分查找，输入目标数值，找出在数组中的索引
func binarySearch(arr []int, target int) (index int, searchCount int) {
	low, high := 0, len(arr)-1
	left, right := low, high
	searchCount = 1
	for left < right {
		searchCount++
		midIndex := left + (right-left)/2
		tmp := arr[midIndex]
		if target == tmp {
			return midIndex, searchCount
		} else if target > tmp {
			left = midIndex - 1
		} else if target < tmp {
			right = midIndex + 1
		}
	}

	//如果没有找到返回负数
	return -1, searchCount
}
